package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 * 执行用时：2 ms, 在所有 Java 提交中击败了97.97%的用户
 * 内存消耗：38.5 MB, 在所有 Java 提交中击败了45.89%的用户
 **/
public class No007 {

    private int[] preorder;
    private Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(0, 0, inorder.length - 1);
    }

    /**
     * 回溯
     *
     * @param root  根节点索引
     * @param left  左边界索引
     * @param right 右边界索引
     * @return 子树根节点
     */
    private TreeNode helper(int root, int left, int right) {
        if (left > right) return null;
        int rootVal = preorder[root];
        TreeNode treeNode = new TreeNode(rootVal);
        int inorderIdx = map.get(rootVal);
        treeNode.left = helper(root + 1, left, inorderIdx - 1);
        treeNode.right = helper(inorderIdx - left + root + 1, inorderIdx + 1, right);
        return treeNode;
    }


}
